// 01背包模板
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int n, V;
int dp[N], v[N], w[N];

int main()
{
    cin >> n >> V;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];
    // (1)
    for (int i = 1; i <= n; i++)
        for (int j = V; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    cout << dp[V] << endl;

    // (2)
    memset(dp, 0, sizeof dp);
    for (int i = 1; i <= V; i++) dp[i] = -1;
    for (int i = 1; i <= n; i++)
        for (int j = V; j >= v[i]; j--)
            if (dp[j - v[i]] != -1) 
                dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    cout << (dp[V] == -1 ? 0 : dp[V]) << endl;
    return 0;
}

// 分割等和子集
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size(), sum = 0;
        for (int e : nums) sum += e;
        if (sum % 2) return false;
        int m = sum / 2;
        vector<bool> dp(m + 1);
        dp[0] = true;
        for (int i = 1; i <= n; i++)
            for (int j = m; j >= nums[i - 1]; j--)
                dp[j] = dp[j] || dp[j - nums[i - 1]];
        return dp[m];
    }
}; 

// 目标和
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int n = nums.size(), sum = 0;
        for (int e : nums) sum += e;
        int m = (target + sum) / 2;
        if (m < 0 || (target + sum) % 2) return 0;
        vector<int> dp(m + 1);
        dp[0] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = m; j >= nums[i - 1]; j--)
                dp[j] += dp[j - nums[i - 1]];
        return dp[m];
    }
};

// 最后一块石头的重量
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for (int e : stones) sum += e;
        int m = sum / 2;
        int n = stones.size();
        vector<int> dp(m + 1);
        for (int i = 1; i <= n; i++)
            for (int j = m; j >= stones[i - 1]; j--)
                dp[j] = max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);
        return sum - 2 * dp[m];
    }
};
    
// 1和0
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int len = strs.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= len; i++)
        {
            int a = 0, b = 0;
            for (auto e : strs[i - 1])
                if (e == '0') a++;
                else b++;
            for (int j = m; j >= a; j--)
                for (int k = n; k >= b; k--)
                    dp[j][k] = max(dp[j][k], dp[j - a][k - b] + 1);
        }
        return dp[m][n];
    }
};

// 盈利计划
class Solution {
public:
    int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p) 
    {
        const int mod = 1e9 + 7;
        int len = g.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1));
        for (int i = 0; i <= n; i++) dp[i][0] = 1;
        for (int i = 1; i <= len; i++)
            for (int j = n; j >= g[i - 1]; j--)
                for (int k = m; k >= 0; k--)
                    dp[j][k] = (dp[j][k] + dp[j - g[i - 1]][max(0, k - p[i - 1])]) % mod;
        return dp[n][m];
    }
};
    
    